#ifndef __BFS__
#define __BFS__

#include "meta_search.hpp"

namespace graph_search{
    class bfs:public search{
        public:
            bfs(){}
            int find(const std::vector<std::vector<int>>& matrix,Position start,Position end){
                int numRows = matrix.size();
                int numCols = matrix.at(0).size();

                std::vector<std::vector<bool>> visited(numRows,std::vector<bool>(numCols,false));
                std::queue<Position> q;
                q.push(start);
                visited[start.x][start.y] = true;

                while (!q.empty())
                {
                    Position currPos = q.front();
                    q.pop();

                    std::cout << "Visiting:(" << currPos.x << ", " <<currPos.y << ")==" << matrix[currPos.x][currPos.y] << std::endl;

                    for(int i=0;i<4;i++){
                        int newX = currPos.x + dx[i];
                        int newY = currPos.y + dy[i];

                        if(newX >= 0 && newX < numRows && newY >= 0 && newY < numCols && !visited[newX][newY]){
                            visited[newX][newY] = true;
                            q.push(Position(newX,newY));
                        }
                    }
                }
            }
    };
}

#endif